"""
校园新生指引程序 - 路线规划模块
实现最短路径算法和自然语言路线描述
"""

import heapq
from typing import List, Dict, Tuple, Optional
from models import CampusMap, Point, Road


class PathFinder:
    """路线规划器，基于Dijkstra算法"""
    
    def __init__(self, campus_map: CampusMap):
        self.campus_map = campus_map
        self.max_retry_count = 3  # 最大重试次数
    
    def validate_input_points(self, start_point_name: str, target_function: str = None, end_point_name: str = None) -> bool:
        """验证输入参数的有效性"""
        if not start_point_name or not start_point_name.strip():
            raise ValueError("起点点位名称不能为空")
        
        if not target_function and not end_point_name:
            raise ValueError("必须指定目标功能或目标点位")
        
        if target_function and end_point_name:
            raise ValueError("不能同时指定目标功能和目标点位")
        
        start_point = self.campus_map.get_point_by_name(start_point_name)
        if not start_point:
            raise ValueError(f"起点点位 '{start_point_name}' 不存在")
        
        if target_function:
            target_points = self.campus_map.get_points_by_function(target_function)
            if not target_points:
                raise ValueError(f"没有提供功能 '{target_function}' 的点位")
        elif end_point_name:
            end_point = self.campus_map.get_point_by_name(end_point_name)
            if not end_point:
                raise ValueError(f"终点点位 '{end_point_name}' 不存在")
        
        return True
    
    def find_route_with_fallback(self, start_point_name: str, target_function: str = None, end_point_name: str = None, retry_count: int = 0) -> Optional[str]:
        """带重试机制的路线规划"""
        try:
            return self.find_route_by_function(start_point_name, target_function) if target_function else self.find_route_by_point(start_point_name, end_point_name)
        except Exception as e:
            if retry_count < self.max_retry_count:
                print(f"路线规划失败，正在重试 ({retry_count + 1}/{self.max_retry_count}): {e}")
                return self.find_route_with_fallback(start_point_name, target_function, end_point_name, retry_count + 1)
            else:
                raise RuntimeError(f"路线规划失败，已重试{self.max_retry_count}次: {e}")
    
    def build_graph(self) -> Dict[str, List[Tuple[str, float]]]:
        """构建图结构，用于路径搜索"""
        graph = {}
        
        # 初始化所有点位
        for point_id in self.campus_map.points:
            graph[point_id] = []
        
        # 添加道路连接
        for road in self.campus_map.roads.values():
            # 双向连接
            graph[road.point1_id].append((road.point2_id, road.distance))
            graph[road.point2_id].append((road.point1_id, road.distance))
        
        return graph
    
    def find_shortest_path(self, start_point_id: str, end_point_id: str) -> Tuple[List[str], float]:
        """
        使用Dijkstra算法查找最短路径
        返回：(路径点位ID列表, 总距离)
        """
        graph = self.build_graph()
        
        # 初始化距离和前驱节点
        distances = {point_id: float('inf') for point_id in graph}
        previous = {point_id: None for point_id in graph}
        distances[start_point_id] = 0
        
        # 优先队列
        priority_queue = [(0, start_point_id)]
        
        while priority_queue:
            current_distance, current_point = heapq.heappop(priority_queue)
            
            # 如果找到目标点位
            if current_point == end_point_id:
                break
            
            # 如果当前距离大于已知最短距离，跳过
            if current_distance > distances[current_point]:
                continue
            
            # 遍历邻居
            for neighbor, weight in graph[current_point]:
                distance = current_distance + weight
                
                if distance < distances[neighbor]:
                    distances[neighbor] = distance
                    previous[neighbor] = current_point
                    heapq.heappush(priority_queue, (distance, neighbor))
        
        # 构建路径
        if distances[end_point_id] == float('inf'):
            return [], float('inf')  # 没有路径
        
        path = []
        current = end_point_id
        while current is not None:
            path.append(current)
            current = previous[current]
        
        path.reverse()
        return path, distances[end_point_id]
    
    def generate_route_description(self, path: List[str]) -> str:
        """生成自然语言路线描述"""
        if len(path) < 2:
            return "您已经在目标位置"
        
        description_parts = []
        
        # 起点描述
        start_point = self.campus_map.points[path[0]]
        description_parts.append(f"从 {start_point.name} 出发")
        
        # 中间路径描述
        for i in range(len(path) - 1):
            current_point_id = path[i]
            next_point_id = path[i + 1]
            
            current_point = self.campus_map.points[current_point_id]
            next_point = self.campus_map.points[next_point_id]
            
            # 查找连接的道路
            road = None
            for r in self.campus_map.roads.values():
                if (r.point1_id == current_point_id and r.point2_id == next_point_id) or \
                   (r.point1_id == next_point_id and r.point2_id == current_point_id):
                    road = r
                    break
            
            if road:
                # 计算方向（简单基于坐标）
                dx = next_point.x - current_point.x
                dy = next_point.y - current_point.y
                
                direction = self._get_direction_description(dx, dy)
                
                step_desc = f"经过 {current_point.name}，{direction}步行约 {int(road.distance)} 米"
                if road.description:
                    step_desc += f"（{road.description}）"
                step_desc += f"，到达 {next_point.name}"
                
                description_parts.append(step_desc)
        
        # 终点描述
        end_point = self.campus_map.points[path[-1]]
        description_parts.append(f"已到达目标位置：{end_point.name}")
        
        return " → ".join(description_parts)
    
    def _get_direction_description(self, dx: float, dy: float) -> str:
        """根据坐标差生成方向描述"""
        if abs(dx) > abs(dy):
            if dx > 0:
                return "向东"
            else:
                return "向西"
        else:
            if dy > 0:
                return "向北"
            else:
                return "向南"
    
    def find_route_by_function(self, start_point_name: str, target_function: str) -> Optional[str]:
        """
        根据起点点位名称和目标功能查找路线
        返回：自然语言路线描述
        """
        # 查找起点点位
        start_point = self.campus_map.get_point_by_name(start_point_name)
        if not start_point:
            return f"未找到点位：{start_point_name}"
        
        # 查找目标功能对应的点位
        target_points = self.campus_map.get_points_by_function(target_function)
        if not target_points:
            return f"未找到提供功能 '{target_function}' 的点位"
        
        # 如果只有一个目标点位，直接规划路线
        if len(target_points) == 1:
            target_point = target_points[0]
            path, distance = self.find_shortest_path(start_point.id, target_point.id)
            if path:
                return self.generate_route_description(path)
            else:
                return f"无法从 {start_point_name} 到达 {target_point.name}"
        
        # 如果有多个目标点位，选择最近的
        best_path = None
        best_distance = float('inf')
        best_target = None
        
        for target_point in target_points:
            path, distance = self.find_shortest_path(start_point.id, target_point.id)
            if path and distance < best_distance:
                best_path = path
                best_distance = distance
                best_target = target_point
        
        if best_path:
            return self.generate_route_description(best_path)
        else:
            return f"无法从 {start_point_name} 到达任何提供功能 '{target_function}' 的点位"
    
    def find_route_by_point(self, start_point_name: str, end_point_name: str) -> Optional[str]:
        """
        根据起点和终点点位名称查找路线
        返回：自然语言路线描述
        """
        start_point = self.campus_map.get_point_by_name(start_point_name)
        end_point = self.campus_map.get_point_by_name(end_point_name)
        
        if not start_point:
            return f"未找到起点点位：{start_point_name}"
        if not end_point:
            return f"未找到终点点位：{end_point_name}"
        
        path, distance = self.find_shortest_path(start_point.id, end_point.id)
        if path:
            return self.generate_route_description(path)
        else:
            return f"无法从 {start_point_name} 到达 {end_point_name}"
